"""
Problem 64: https://projecteuler.net/problem=64

All square roots are periodic when written as continued fractions.
For example, let us consider sqrt(23).
It can be seen that the sequence is repeating.
For conciseness, we use the notation sqrt(23)=[4;(1,3,1,8)],
to indicate that the block (1,3,1,8) repeats indefinitely.
Exactly four continued fractions, for N<=13, have an odd period.
How many continued fractions for N<=10000 have an odd period?

References:
- https://en.wikipedia.org/wiki/Continued_fraction
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/20
'''




from commonfuncs.continuedfractionsSQRT import continuedfractionsSQRT
def solution(limit: int = 10000):
    return sum([len((continuedfractionsSQRT(i))[1]) % 2
                for i in range(1, limit+1)])


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 1322

    print(max(len(continuedfractionsSQRT(i)[1]) for i in range(10000)))
    # max period is 217, when n<100000
